package ljl.alg.wangzheng_camp.round1.bisection;

public class _852_mountain_arr {
    
    /**
     * 遍历自然是可以的
     * 但是期望你用二分
     *
     * */
    public int peakIndexInMountainArray_shabi(int[] arr) {
        int l = 1, r = arr.length - 2;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            int left = arr[mid - 1], cur = arr[mid], right = arr[mid + 1];
            if (left < cur && cur > right) return mid;
            if (cur > right) {
                r = mid - 1;
            }
            else if (cur > left){
                l = mid + 1;
            }
        }
        return 8848;
    }
    
    /**
     * 很鸡贼。
     * 只和右边比。
     * 如果是升序，一直往右走。
     * 如果是降序，当前位置可能是答案，记录，然后往左走
     *
     * 简而言之，找到最左边的那个值。
     * */
    public int peakIndexInMountainArray(int[] arr) {
        int l = 1, r = arr.length - 2;
        int res = 0;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (arr[mid] > arr[mid + 1]) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
    
    
}
